package com.hy;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:被围绕的区域
 * 给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
 * User:Mr.Du
 * Date:2023/8/25
 * Time:17:13
 */
public class Solve {

    public static void main(String[] args) {
        char[][] board = {
                {'X', 'X', 'X', 'X'},
                {'X', 'O', 'O', 'X'},
                {'O', 'X', 'O', 'X'},
                {'X', 'O', 'X', 'X'}
        };
        solve(board);
        printArray2(board);

        System.out.println(Integer.MIN_VALUE);
    }

    public static void solve(char[][] board) {
        int m = board.length, n = board[0].length;
        for(int i = 0;i < m;i++){
            if(board[i][0] == 'O') dfs(board, i, 0, m, n);
            if(board[i][n - 1] == 'O') dfs(board, i,  n - 1, m, n);

        }
        for(int i = 0;i < n;i++){
            if(board[0][i] == 'O') dfs(board, 0, i, m, n);
            if(board[m-1][i] == 'O') dfs(board, m - 1, i, m, n);
        }
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                if(board[i][j] == 'O') board[i][j] = 'X';
                if(board[i][j] == 'P') board[i][j] = 'O';
            }
        }

    }

    public static void dfs(char[][] board, int i, int j, int m, int n){
        if(i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'O') return;
        board[i][j] = 'P';
        dfs(board, i, j + 1, m, n);
        dfs(board, i, j - 1, m, n);
        dfs(board, i + 1, j, m, n);
        dfs(board, i - 1, j, m, n);
    }

    public static void printArray2(char[][] board){
        int m = board.length, n = board[0].length;
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                System.out.print(board[i][j] + " ");
            }
            System.out.println();
        }
    }
}
